/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：最长上升子序列</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/
 * </pre>
 * <p>创建日期：2019年11月22日上午10:54:02</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code300LongestIncreasingSubsequence</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code300LongestIncreasingSubsequence
{
	public static void main(String[] args)
	{
		/**
		 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。

		示例:
		输入: [10,9,2,5,3,7,101,18]
		输出: 4 
		解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
		
		说明:
		可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
		你算法的时间复杂度应该为 O(n2) 。
		进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
		 */
		int increasingSubsequence = longestIncreasingSubsequence(new int[] { 10, 9, 2, 5, 3, 7, 101, 18 });
		System.out.println(increasingSubsequence);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		若dp[i]表示到nums[i]的最大上升子序列长度，且包含nums[i]
	 * 		即排除元素num[i],在i之前，必有最长的子序列和nums[i]构成最长的上升子序列
	 * 		也即循环记录每个以nums[i]作为末端字符的上升子串的长度，取出里面的最长的即可
	 * 		则：
	 * 			dp[i]=max(dp[j])+1,0<=j<i
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(n)
	 * 
	 * @param nums
	 * @return
	 */
	public static int longestIncreasingSubsequence(int[] nums)
	{
		//1.判空
		if (nums == null || nums.length <= 0)
		{
			return 0;
		}
		//2.初始化dp数组
		int[] dp = new int[nums.length];
		//3.初始化开口值dp[0]
		dp[0] = 1;
		//4.初始化长度默认值
		int max = 1;
		//5.外层循环表示dp[i],以num[i]元素作为结尾的子序列的长度
		for (int i = 1; i < dp.length; i++)
		{
			//6.初始化每一轮比较的最大长度值
			int maxVal = 0;
			//7.内层循环表示dp[i]之前可能和num[i]构成的最长子序列的值dp[j]
			for (int j = 0; j < i; j++)
			{
				//8.如果num[i]大于nums[j]，则取此时的dp[j]和maxVal的最大值，即取最长的序列
				if (nums[i] > nums[j])
				{
					maxVal = Math.max(maxVal, dp[j]);
				}
			}
			//9.由于maxVal表示的是以nums[i]作为结尾的最长子序列的值，因此dp[i]=maxVal+1
			dp[i] = maxVal + 1;
			//10.取每个以nums[i]作为结尾的子序列的最大长度
			max = Math.max(max, dp[i]);
		}
		return max;
	}
}
